package com.leetcode.www;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。
 *
 * 编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-transformer-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-12
 * Time:16:58
 */
public class Interview17_22 {
    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        Map<String, String> vis = new HashMap<>();
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        vis.put(beginWord, beginWord);
        Stack<String> stk = new Stack<>();//逆序存栈
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                if (cur.equals(endWord)) {
                    stk.push(endWord);
                    String t = endWord;
                    while (!t.equals(beginWord)) {
                        t = vis.get(t);
                        stk.push(t);
                    }
                    List<String> res = new ArrayList<>();
                    while (!stk.isEmpty()) res.add(stk.pop());//倒出栈元素
                    return res;
                }

                for (String next : words) {
                    if (isNext(cur, next) && !vis.containsKey(next)) {
                        vis.put(next, cur);
                        q.offer(next);
                    }
                }
            }
        }
        return new ArrayList<>();

    }


    /**
     * 遍历两个相同长度相同的字符，判断是否不相同的字符差1个
     *
     * @param cur  当前字母
     * @param next 候选字母
     * @return
     */
    public boolean isNext(String cur, String next) {
        int cnt = 0;
        for (int i = 0; i < cur.length(); i++) {
            if (cur.charAt(i) != next.charAt(i)) cnt++;
        }
        return cnt == 1;
    }

    public List<String> findLadders2(String beginWord, String endWord, List<String> wordList) {
        //定义BFS的队列
        Queue<String> queue = new LinkedList<String>();
        //ans存放答案
        List<String> ans = new LinkedList<String>();
        //标记是否被访问过
        boolean[] visited = new boolean[wordList.size()];
        //存放每个单词的前驱，比如hot的前驱可以是hit,lot等；
        HashMap<String,String> map = new HashMap<String,String>();
        //初步判断
        if(!wordList.contains(endWord)){
            return ans;
        }
        //将第一个单词加入队列
        queue.add(beginWord);
        boolean flag = false;
        //BFS主要操作
        while(queue.size() != 0){
            //先将头取出
            String queueHead = queue.poll();
            //如果队列头元素等于endword，代表已经找到，break同时设置flag = true;
            if(queueHead.equals(endWord)){
                flag = true;
                break;
            }
            //寻找可能的元素加入队列，并且设置对应的前驱。
            for(int i = 0;i < wordList.size();i ++){
                //如果未被访问过并且可以直接转换，则加入队列，compare()函数用来判断是否可以转换。
                if(visited[i] == false && compare(wordList.get(i),queueHead) == true){
                    queue.add(wordList.get(i));
                    visited[i] = true;
                    //存储前驱
                    map.put(wordList.get(i), queueHead);
                }
            }
        }
        if(flag == false){
            return ans;
        }

        //遍历答案
        String key = endWord;
        while(map.get(key) != beginWord){
            ans.add(key);
            key = map.get(key);
        }
        ans.add(key);
        ans.add(map.get(key));
        Collections.reverse(ans);
        return ans;
    }
    public static boolean compare(String word1,String word2){
        int diff = 0;
        for(int i = 0;i < word1.length();i ++){
            if(word1.charAt(i) != word2.charAt(i)){
                diff ++;
                if(diff >= 2){
                    return false;
                }
            }
        }
        return true;
    }
}
